{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Champagne Tower"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: champagneTower"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #香槟塔"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>我们把玻璃杯摆成金字塔的形状，其中&nbsp;<strong>第一层</strong>&nbsp;有 <code>1</code> 个玻璃杯， <strong>第二层</strong>&nbsp;有 <code>2</code> 个，依次类推到第 100 层，每个玻璃杯 (250ml) 将盛有香槟。</p>\n",
    "\n",
    "<p>从顶层的第一个玻璃杯开始倾倒一些香槟，当顶层的杯子满了，任何溢出的香槟都会立刻等流量的流向左右两侧的玻璃杯。当左右两边的杯子也满了，就会等流量的流向它们左右两边的杯子，依次类推。（当最底层的玻璃杯满了，香槟会流到地板上）</p>\n",
    "\n",
    "<p>例如，在倾倒一杯香槟后，最顶层的玻璃杯满了。倾倒了两杯香槟后，第二层的两个玻璃杯各自盛放一半的香槟。在倒三杯香槟后，第二层的香槟满了 - 此时总共有三个满的玻璃杯。在倒第四杯后，第三层中间的玻璃杯盛放了一半的香槟，他两边的玻璃杯各自盛放了四分之一的香槟，如下图所示。</p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://s3-lc-upload.s3.amazonaws.com/uploads/2018/03/09/tower.png\" style=\"height: 241px; width: 350px;\" /></p>\n",
    "\n",
    "<p>现在当倾倒了非负整数杯香槟后，返回第 <code>i</code> 行 <code>j</code>&nbsp;个玻璃杯所盛放的香槟占玻璃杯容积的比例（ <code>i</code> 和 <code>j</code>&nbsp;都从0开始）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<pre>\n",
    "<strong>示例 1:</strong>\n",
    "<strong>输入:</strong> poured(倾倒香槟总杯数) = 1, query_glass(杯子的位置数) = 1, query_row(行数) = 1\n",
    "<strong>输出:</strong> 0.00000\n",
    "<strong>解释:</strong> 我们在顶层（下标是（0，0））倒了一杯香槟后，没有溢出，因此所有在顶层以下的玻璃杯都是空的。\n",
    "\n",
    "<strong>示例 2:</strong>\n",
    "<strong>输入:</strong> poured(倾倒香槟总杯数) = 2, query_glass(杯子的位置数) = 1, query_row(行数) = 1\n",
    "<strong>输出:</strong> 0.50000\n",
    "<strong>解释:</strong> 我们在顶层（下标是（0，0）倒了两杯香槟后，有一杯量的香槟将从顶层溢出，位于（1，0）的玻璃杯和（1，1）的玻璃杯平分了这一杯香槟，所以每个玻璃杯有一半的香槟。\n",
    "</pre>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" /></p>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> poured = 100000009, query_row = 33, query_glass = 17\n",
    "<strong>输出:</strong> 1.00000\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;=&nbsp;poured &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>0 &lt;= query_glass &lt;= query_row&nbsp;&lt; 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [champagne-tower](https://leetcode.cn/problems/champagne-tower/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [champagne-tower](https://leetcode.cn/problems/champagne-tower/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1\\n1\\n1', '2\\n1\\n1', '100000009\\n33\\n17']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        remain = [poured]\n",
    "        for r in range(query_row):\n",
    "            overflow = False\n",
    "            newRemain = [0] * (r + 2)\n",
    "            for i in range(r + 1):\n",
    "                if remain[i] > 1:\n",
    "                    over = (remain[i] - 1) / 2\n",
    "                    newRemain[i] += over\n",
    "                    newRemain[i + 1] += over\n",
    "                    overflow = True\n",
    "            remain = newRemain\n",
    "            if not overflow:\n",
    "                break\n",
    "        if len(remain) < query_row + 1:\n",
    "            return 0\n",
    "        else:\n",
    "            return min(remain[query_glass], 1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured, query_row, query_glass):\n",
    "        \"\"\"\n",
    "        :type poured: int\n",
    "        :type query_row: int\n",
    "        :type query_glass: int\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        row, flag, index = [[poured]], True if poured > 1 else False, 0\n",
    "        while flag and index <= query_row:\n",
    "            temp = [0] * (len(row[-1]) + 1)\n",
    "            for i in range(len(row[-1])):\n",
    "                if row[-1][i] > 1:\n",
    "                    temp[i] += (row[-1][i] - 1) / 2\n",
    "                    temp[i + 1] += (row[-1][i] - 1) / 2\n",
    "                    row[-1][i] = 1\n",
    "            row.append(temp)\n",
    "            flag = any(t > 1 for t in temp)\n",
    "            index += 1\n",
    "        if query_row >= len(row):\n",
    "            return 0\n",
    "        return row[query_row][query_glass]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured, query_row, query_glass):\n",
    "        \"\"\"\n",
    "        :type poured: int\n",
    "        :type query_row: int\n",
    "        :type query_glass: int\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        #就模拟过程，本身结构就有DP特征，所以其实也不需要特别注意DP了\n",
    "        capacity=[[0]*101 for i in range(101)]\n",
    "        capacity[0][0] = poured\n",
    "        for i in range(query_row+1):\n",
    "            for j in range(i+1):\n",
    "                remain = (capacity[i][j] - 1.0) / 2\n",
    "                if remain>0:\n",
    "                    capacity[i+1][j] += remain\n",
    "                    capacity[i+1][j+1] += remain\n",
    "        return min(capacity[query_row][query_glass], 1.0)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured, query_row, query_glass):\n",
    "        \"\"\"\n",
    "        :type poured: int\n",
    "        :type query_row: int\n",
    "        :type query_glass: int\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        if poured==0:return 0\n",
    "        re=[]\n",
    "        if (query_row, query_glass)==(0,0):\n",
    "            return 1\n",
    "        n=max(query_row,query_glass)+1\n",
    "        for i in range(n):\n",
    "            re.append([])\n",
    "            for j in range(i+1):\n",
    "                re[i].append([0,0])\n",
    "        re[0][0]=[1,poured-1]\n",
    "        poured-=1\n",
    "        r,c=query_row, query_glass\n",
    "        for i in range(1,n):\n",
    "            for j in range(i+1):\n",
    "                if j==0:\n",
    "                    re[i][j][0]=re[i-1][0][1]/2\n",
    "                elif j==i:\n",
    "                    re[i][j][0]=re[i-1][j-1][1]/2\n",
    "                else:\n",
    "                    re[i][j][0]=re[i-1][j-1][1]/2+re[i-1][j][1]/2\n",
    "                if re[i][j][0]>1:\n",
    "                    re[i][j][1]=re[i][j][0]-1\n",
    "                    re[i][j][0]=1\n",
    "        return re[r][c][0]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        glasses = [[0.0] * (i + 1) for i in range(100)]\n",
    "        glasses[0][0] = float(poured)\n",
    "        for i in range(1, query_row + 1):\n",
    "            for j in range(i + 1):\n",
    "                l = r = 0.0\n",
    "                if j > 0:\n",
    "                    l = max(0.0, glasses[i - 1][j - 1] - 1)\n",
    "                if j < i:\n",
    "                    r = max(0.0, glasses[i - 1][j] - 1)\n",
    "                glasses[i][j] = (l + r) / 2\n",
    "        return min(1.0, glasses[query_row][query_glass])\n",
    "\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        glasses = [[0.0] * (i + 1) for i in range(query_row + 1)]\n",
    "        glasses[0][0] = float(poured)\n",
    "        for i in range(query_row):\n",
    "            for j in range(i + 1):\n",
    "                extra = (glasses[i][j] - 1.0) / 2\n",
    "                if extra > 0:\n",
    "                    glasses[i + 1][j] += extra\n",
    "                    glasses[i + 1][j + 1] += extra\n",
    "        return min(1.0, glasses[query_row][query_glass])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        glasses = [[0.0] * (i + 1) for i in range(100)]\n",
    "        glasses[0][0] = float(poured)\n",
    "        for i in range(1, query_row + 1):\n",
    "            for j in range(i + 1):\n",
    "                l = r = 0.0\n",
    "                if j > 0:\n",
    "                    l = max(0.0, glasses[i - 1][j - 1] - 1)\n",
    "                if j < i:\n",
    "                    r = max(0.0, glasses[i - 1][j] - 1)\n",
    "                glasses[i][j] = (l + r) / 2\n",
    "        return min(1.0, glasses[query_row][query_glass])\n",
    "\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        glasses = [[0.0] * (i + 1) for i in range(query_row + 1)]\n",
    "        glasses[0][0] = float(poured)\n",
    "        for i in range(query_row):\n",
    "            for j in range(i + 1):\n",
    "                extra = (glasses[i][j] - 1.0) / 2\n",
    "                if extra > 0:\n",
    "                    glasses[i + 1][j] += extra\n",
    "                    glasses[i + 1][j + 1] += extra\n",
    "        return min(1.0, glasses[query_row][query_glass])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def update(pour):\n",
    "    if pour<=1:\n",
    "        return 0, 0\n",
    "    else:\n",
    "        son = (pour-1)/2\n",
    "        return son, son\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        glass = [poured]\n",
    "        for i in range(1,query_row+1):\n",
    "            next_glasses = [0]*(i+1)\n",
    "            for i,x in enumerate(glass):\n",
    "                left, right = update(x)\n",
    "                next_glasses[i]+=left\n",
    "                next_glasses[i+1]+=right\n",
    "            glass = next_glasses\n",
    "        \n",
    "        res = glass[query_glass]\n",
    "        return res if res<=1 else 1\n",
    "            \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        dp = [[0 for i in range(100)] for j in  range(100)]\n",
    "        dp[0][0]= poured\n",
    "        maxRow = min(poured, 99) + 1\n",
    "\n",
    "        for i in range(0, maxRow):\n",
    "            break_flag = True\n",
    "            if i == 0:\n",
    "                continue\n",
    "            for j in range(maxRow):\n",
    "                if dp[i-1][j] > 1:\n",
    "                    overflow = dp[i - 1][j] - 1\n",
    "                    dp[i - 1][j] = 1\n",
    "                    dp[i][j] += (overflow / 2)\n",
    "                    dp[i][j + 1] += (overflow / 2)\n",
    "                    break_flag = False\n",
    "                else:\n",
    "                    continue\n",
    "            if break_flag:\n",
    "                break\n",
    "\n",
    "        return dp[query_row][query_glass]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        dp = [[0]*100 for i in range(100)]\n",
    "\n",
    "        dp[0][0] = poured\n",
    "\n",
    "        for i in range(1, query_row+1):\n",
    "            for j in range(query_glass+1):\n",
    "                if dp[i-1][j] >= 1:\n",
    "                    dp[i][j] += (dp[i-1][j]-1)/2\n",
    "                if j>0 and dp[i-1][j-1] >= 1:\n",
    "                    dp[i][j] += (dp[i-1][j-1]-1)/2\n",
    "        \n",
    "        res = dp[query_row][query_glass]\n",
    "        if res >= 1:\n",
    "            return 1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        dp = [[0 for _ in range(x)] for x in range(1, query_row + 2)]\n",
    "        dp[0][0] = poured \n",
    "\n",
    "        for i in range(query_row):\n",
    "            for j in range(len(dp[i])):\n",
    "                temp = (dp[i][j] - 1) / 2.0\n",
    "                if temp > 0:\n",
    "                    dp[i + 1][j] += temp\n",
    "                    dp[i + 1][j + 1] += temp \n",
    "        \n",
    "        return dp[query_row][query_glass] if dp[query_row][query_glass] < 1 else 1.0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        A = [[0]*k for k in range(1, 102)]\n",
    "        A[0][0]=poured\n",
    "        for r in range(query_row + 1):\n",
    "            for c in range(r+1):\n",
    "                q = (A[r][c] - 1.0) / 2.0\n",
    "                if q>0:\n",
    "                    A[r+1][c]+=q\n",
    "                    A[r+1][c+1]+=q\n",
    "        return min(1, A[query_row][query_glass])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        l_list = [[0 for _ in range(101)] for _ in range(101)]\n",
    "        l_list[0][0] = poured\n",
    "        for i in range(query_row):\n",
    "            for j in range(i + 1):\n",
    "                if l_list[i][j] > 1:\n",
    "                    l_list[i+1][j] += (l_list[i][j] - 1) / 2\n",
    "                    l_list[i+1][j + 1] += (l_list[i][j] - 1) / 2\n",
    "            print(l_list[i][:(i+1)])\n",
    "        return min(l_list[query_row][query_glass], 1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        ans=[[[0,0] for _ in range(query_row+2)] for __ in range(query_row+1)]\n",
    "        if poured>1: ans[0][1]=[1,(poured-1)/2]\n",
    "        else: ans[0][1]=[poured,0]\n",
    "        for i in range(1,query_row+1):\n",
    "            for j in range(1,i+2):\n",
    "                pour=ans[i-1][j-1][1]+ans[i-1][j][1]\n",
    "                if pour>1:\n",
    "                    ans[i][j]=[1,(pour-1)/2]\n",
    "                else: ans[i][j]=[pour,0]\n",
    "        return ans[query_row][query_glass+1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        row = [poured]\n",
    "\n",
    "        for i in range(1, query_row+1):\n",
    "            nextrow = [0] * (i+1)\n",
    "            for j, volume in enumerate(row):\n",
    "                if volume > 1:\n",
    "                    nextrow[j] += (volume - 1) / 2\n",
    "                    nextrow[j+1] += (volume - 1) / 2\n",
    "            row = nextrow\n",
    "\n",
    "        return min(1, row[query_glass])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        row_start = [poured]\n",
    "        for i in range(1, query_row+1):\n",
    "            row_end = [0]*(i+1)\n",
    "            for t, v in enumerate(row_start):\n",
    "                if v>1:\n",
    "                    row_end[t]+=(v-1)/2\n",
    "                    row_end[t+1]+=(v-1)/2\n",
    "            row_start = row_end\n",
    "        return min(1, row_start[query_glass])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        f = [poured]\n",
    "        for i in range(1, query_row + 1):\n",
    "            g = [0] * (i + 1)\n",
    "            for j, v in enumerate(f):\n",
    "                if v > 1:\n",
    "                    half = (v - 1) / 2\n",
    "                    g[j] += half\n",
    "                    g[j + 1] += half\n",
    "            f = g\n",
    "        return min(1, f[query_glass])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        n=query_row\n",
    "        dp=[[0]*(n+1) for _ in range(n+1)]\n",
    "        dp[0][0]=poured\n",
    "        for i in range(n):\n",
    "            for j in range(n+1):\n",
    "                if dp[i][j]>1:\n",
    "                    dp[i+1][j]+=(dp[i][j]-1)/2\n",
    "                    dp[i+1][j+1]+=(dp[i][j]-1)/2\n",
    "                    dp[i][j]=1\n",
    "        # 不要忘记和1取min\n",
    "        return min(1,dp[query_row][query_glass])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        dp = [[0]*(query_row+2) for i in range(query_row+2)]\n",
    "        dp[1][1] = poured\n",
    "        for i in range(2, query_row+2):\n",
    "            for j in range(1, query_row+2):\n",
    "                dp[i][j] = max(dp[i-1][j-1]-1, 0)/2+max(dp[i-1][j]-1, 0)/2\n",
    "        return min(dp[query_row+1][query_glass+1], 1)\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        level = [poured]\n",
    "        for row in range(1, query_row+1):\n",
    "            nextlevel = [0] * (row + 1)\n",
    "            for i in range(len(level)):\n",
    "                if level[i] > 1:\n",
    "                    nextlevel[i] += (level[i] - 1) / 2\n",
    "                    nextlevel[i+1] += (level[i] - 1) / 2\n",
    "            level = nextlevel\n",
    "        return min(level[query_glass], 1)\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, row: int, col: int) -> float:\n",
    "        dp=[[0]*101 for i in range(101)]\n",
    "        dp[0][0]=poured\n",
    "        for i in range(row+1):\n",
    "            for j in range(i+1):\n",
    "                if dp[i][j]>1:\n",
    "                    cur=dp[i][j]-1\n",
    "                    dp[i][j]=1\n",
    "                    dp[i+1][j]+=cur/2\n",
    "                    dp[i+1][j+1]+=cur/2\n",
    "        return dp[row][col]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        row = [poured]\n",
    "        for i in range(1, query_row + 1):\n",
    "            nextRow = [0] * (i + 1)\n",
    "            for j, volume in enumerate(row):\n",
    "                if volume > 1:\n",
    "                    nextRow[j] += (volume - 1) / 2\n",
    "                    nextRow[j + 1] += (volume - 1) / 2\n",
    "            row = nextRow\n",
    "        return min(1, row[query_glass])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, k: int, n: int, m: int) -> float:\n",
    "        f = [[0] * (n + 10) for _ in range(n + 10)]\n",
    "        f[0][0] = k\n",
    "        for i in range(n + 1):\n",
    "            for j in range(i + 1):\n",
    "                if f[i][j] <= 1:\n",
    "                    continue\n",
    "                f[i + 1][j] += (f[i][j] - 1) / 2\n",
    "                f[i + 1][j + 1] += (f[i][j] - 1) / 2\n",
    "        return min(f[n][m], 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        m, n = query_row, query_glass\n",
    "\n",
    "        f = [[0] * (m + 2) for _ in range(m + 2)]\n",
    "        f[0][0] = poured\n",
    "\n",
    "        for i in range(m+1):\n",
    "            for j in range(i+1):\n",
    "                if f[i][j] <= 1:\n",
    "                    continue\n",
    "                f[i+1][j] += (f[i][j] - 1) / 2\n",
    "                f[i+1][j+1] += (f[i][j] - 1) / 2\n",
    "\n",
    "        print(f)\n",
    "        return min(1, f[m][n])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        \"\"\"\n",
    "        (i,j)的香槟来自(i-1,j-1)+(i-1,j)\n",
    "        而后可以继续递归 当(i,j)的香槟大于1的时候 才会给下一层\n",
    "        \"\"\"\n",
    "        @lru_cache()\n",
    "        def dfs(i, j):\n",
    "            if j < 0 or j > i:  # 不符合规范的取值\n",
    "                return 0\n",
    "            if i == 0:\n",
    "                return poured\n",
    "            source1 = max(dfs(i - 1, j - 1)-1,0)/2 #上面来的需要倒满自己再平分\n",
    "            source2 = max(dfs(i - 1, j)-1,0)/2\n",
    "            return source1+source2\n",
    "\n",
    "        return min(dfs(query_row, query_glass),1) #最大为1 因为会倒入下一杯"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        d={(0,0):poured}\n",
    "        def get(row,query_glass):\n",
    "            if (row,query_glass) in d:\n",
    "                return d[(row,query_glass)] \n",
    "            l=(get(row-1,query_glass-1)-1)/2 if query_glass>0 else 0\n",
    "            l=max(l,0)\n",
    "            r=(get(row-1,query_glass)-1)/2 if query_glass<row else 0\n",
    "            r=max(r,0)\n",
    "            d[(row,query_glass)]=l+r\n",
    "            return l+r \n",
    "        t=get(query_row,query_glass) \n",
    "        return t if t<1 else 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        @cache\n",
    "        def getFlow(query_row: int, query_glass: int) -> float:\n",
    "            # 越界\n",
    "            if query_glass < 0 or query_glass > query_row:\n",
    "                return 0\n",
    "            # 左半\n",
    "            if query_glass > query_row >> 1:\n",
    "                return getFlow(query_row, query_row - query_glass)\n",
    "            # 根\n",
    "            if query_row == 0:\n",
    "                return poured\n",
    "            left, right = getFlow(query_row - 1, query_glass - 1), getFlow(query_row - 1, query_glass)\n",
    "            return ((left - 1) / 2 if left > 1 else 0) + ((right - 1) / 2 if right > 1 else 0)\n",
    "        flow: float = getFlow(query_row, query_glass)\n",
    "        return flow if flow < 1 else 1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        if not poured: return 0\n",
    "\n",
    "        # 定义dp[i][j]为第i层倒了j杯之后[装的香槟, 溢出的香槟]\n",
    "        dp = []\n",
    "        for _ in range(query_row+1):\n",
    "            row = []\n",
    "            for _ in range(query_row+2):\n",
    "                row.append([0,0])\n",
    "            dp.append(row)\n",
    "\n",
    "        # 倒pour次，第一杯装满，剩余pour-1流到下层\n",
    "        dp[0][1] = [1, poured-1]\n",
    "\n",
    "        # 如果第一层流出来\n",
    "        if dp[0][1][-1]:\n",
    "            for i in range(1, query_row+1):\n",
    "                for j in range(1, i+2):\n",
    "                    res = dp[i-1][j-1][-1]/2 + dp[i-1][j][-1]/2 # 每个杯子接收到上层流出来的量\n",
    "                    dp[i][j] = [min(res, 1), max(res-1, 0)]     # 更新dp， 如果res不够1杯，dp=[res,0]， 否则dp=[1, res-1]\n",
    "        print(dp)\n",
    "        return dp[query_row][query_glass+1][0] # 某行某列杯子装的量"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        if not poured: return 0\n",
    "\n",
    "        # 定义dp[i][j]为第i层倒了j杯之后[装的香槟, 溢出的香槟]\n",
    "        dp = []\n",
    "        for _ in range(query_row+1):\n",
    "            row = []\n",
    "            for _ in range(query_row+2):\n",
    "                row.append([0,0])\n",
    "            dp.append(row)\n",
    "\n",
    "        # 倒pour次，第一杯装满，剩余pour-1流到下层\n",
    "        dp[0][1] = [1, poured-1]\n",
    "\n",
    "        # 如果第一层流出来\n",
    "        if dp[0][1][-1]:\n",
    "            for i in range(1, query_row+1):\n",
    "                for j in range(1, i+2):\n",
    "                    res = dp[i-1][j-1][-1]/2 + dp[i-1][j][-1]/2 # 每个杯子接收到上层流出来的量\n",
    "                    dp[i][j] = [min(res, 1), max(res-1, 0)]     # 更新dp， 如果res不够1杯，dp=[res,0]， 否则dp=[1, res-1]\n",
    "        print(dp)\n",
    "        return dp[query_row][query_glass+1][0] # 某行某列杯子装的量"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        if query_glass>query_row-query_glass:\n",
    "            query_glass=query_row-query_glass\n",
    "        @cache\n",
    "        def flow(query_row,query_glass):\n",
    "            if query_row==0:\n",
    "                return poured\n",
    "\n",
    "            if query_glass>query_row-query_glass:\n",
    "                return flow(query_row,query_row-query_glass)\n",
    "\n",
    "            ans=0.0\n",
    "            if query_glass>0:\n",
    "                tmp=flow(query_row-1,query_glass-1)\n",
    "                if tmp>1:\n",
    "                    ans+=(tmp-1)/2\n",
    "            tmp=flow(query_row-1,query_glass)\n",
    "            if tmp>1:\n",
    "                ans+=(tmp-1)/2\n",
    "            return ans\n",
    "        flowans=flow(query_row,query_glass)\n",
    "        if flowans>1:\n",
    "            return 1.0\n",
    "        return flowans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:\n",
    "        n=poured\n",
    "\n",
    "        class node():\n",
    "\n",
    "            def __init__(self):\n",
    "\n",
    "                self.sj=0\n",
    "\n",
    "                self.yc=0\n",
    "\n",
    "\n",
    "\n",
    "        a=100\n",
    "\n",
    "        b=[]\n",
    "\n",
    "        for i in range(a):\n",
    "\n",
    "            tmp=[]    \n",
    "\n",
    "            for j in range(a):\n",
    "\n",
    "                tmp.append(node())\n",
    "\n",
    "            b.append(tmp)\n",
    "\n",
    "        def get_yc(i,j):\n",
    "\n",
    "            if i<100 and i>=0 and j<100 and j>=0:\n",
    "\n",
    "                return b[i][j].yc/2\n",
    "\n",
    "            else:\n",
    "\n",
    "                return 0\n",
    "\n",
    "\n",
    "\n",
    "        for i in range(a):\n",
    "\n",
    "            for j in range(i+1):\n",
    "\n",
    "                if i==0:\n",
    "\n",
    "                    if n>1:\n",
    "\n",
    "                        b[i][j].sj=1\n",
    "\n",
    "                        b[i][j].yc=n-1\n",
    "\n",
    "                    else:\n",
    "\n",
    "                        b[i][j].sj=n\n",
    "\n",
    "                if i>0:\n",
    "\n",
    "                    tmp=get_yc(i-1,j)+get_yc(i-1,j-1)\n",
    "\n",
    "                    if tmp>1:\n",
    "\n",
    "                        b[i][j].sj=1\n",
    "\n",
    "                        b[i][j].yc=tmp-1\n",
    "\n",
    "                    else:\n",
    "\n",
    "                        b[i][j].sj=tmp    \n",
    "\n",
    "        return b[query_row][query_glass].sj\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
